namespace Bread.Utility;

public static class Algorithms
{
    /// <summary>
    /// 折半迭代，二分法迭代
    /// </summary>
    /// <param name="action">0：命中；1：在后面找； -1：在前面找</param>
    /// <returns>0：命中；-1：未命中</returns>
    public static int HalfFind(int count, Func<int, int> action)
    {
        int end = count;
        int begin = 0;
        int mid;
        int result = 0;

        while (begin <= end) {
            mid = (begin + end) / 2;
            if (mid < 0 || mid >= count) return -1;

            result = action(mid);
            if (result == 0)
                return mid;
            else if (result < 0) {
                end = mid - 1;
                continue;
            }
            else {
                begin = mid + 1;
                continue;
            }
        }

        return -1;
    }

    /// <summary>
    /// 判断 [x1, x2] 与 [y1, y2] 两个区间是否有重叠
    /// </summary>
    public static bool HasOverlap(double x1, double x2, double y1, double y2)
    {
        if (x2 < y1) return false;
        if (y2 < x1) return false;
        return true;
    }

    /// <summary>
    /// 移除两个list中的相同部分，保留不同的部分
    /// </summary>
    public static void AcceptDifference<T>(List<T> n1, List<T> n2) where T : IComparable<T>
    {
        if (n1.Count == 0) return;
        if (n2.Count == 0) return;

        for (int i = n1.Count - 1; i >= 0; i--) {
            var v1 = n1[i];
            for (int j = n2.Count - 1; j >= 0; j--) {
                var v2 = n2[j];
                if (v1.CompareTo(v2) == 0) {
                    n2.RemoveAt(j);
                    n1.RemoveAt(i);
                    break;
                }
            }
        }
    }


    /// <summary>
    /// 找出所有重复项 (对大数据量优化)
    /// </summary>
    public static List<T> FindAllDuplicates<T>(List<T> data, Func<T, string> keySelector)
    {
        var indexMap = new Dictionary<string, T>(StringComparer.Ordinal);
        var seenAsDuplicate = new HashSet<string>(StringComparer.Ordinal);
        var duplicates = new List<T>();

        foreach (var item in data) {
            var key = keySelector(item);

            if (indexMap.TryGetValue(key, out var first)) {
                // 确保 first 只添加一次
                if (seenAsDuplicate.Add(key)) {
                    duplicates.Add(first);
                }

                duplicates.Add(item);
            }
            else {
                indexMap[key] = item;
            }
        }

        return duplicates;
    }

    /// <summary>
    /// 找出所有重复项
    /// </summary>
    public static List<T> FindDuplicates<T>(IEnumerable<T> data, Func<T, string> keySelector)
    {
        var indexMap = new Dictionary<string, T>(StringComparer.Ordinal);
        var seenAsDuplicate = new HashSet<string>(StringComparer.Ordinal);
        var duplicates = new List<T>();

        foreach (var item in data) {
            var key = keySelector(item);

            if (indexMap.TryGetValue(key, out var first)) {
                // 确保 first 只添加一次
                if (seenAsDuplicate.Add(key)) {
                    duplicates.Add(first);
                }

                duplicates.Add(item);
            }
            else {
                indexMap[key] = item;
            }
        }

        return duplicates;
    }

    /// <summary>
    /// 找出所有重复项
    /// </summary>
    public static List<V> FindDuplicates<K, V>(this IEnumerable<V> data, Func<V, K> keySelector) where K : notnull
    {
        var indexMap = new Dictionary<K, V>();
        var seenAsDuplicate = new HashSet<K>();
        var duplicates = new List<V>();

        foreach (var item in data) {
            var key = keySelector(item);

            if (indexMap.TryGetValue(key, out var first)) {
                // 确保 first 只添加一次
                if (seenAsDuplicate.Add(key)) {
                    duplicates.Add(first);
                }

                duplicates.Add(item);
            }
            else {
                indexMap[key] = item;
            }
        }

        return duplicates;
    }

    public static int IndexOf<T>(this IEnumerable<T> source, Func<T, bool> selector)
    {
        if (source == null) return -1;
        int index = 0;
        foreach (var item in source) {
            if (selector(item)) return index;
            index++;
        }
        return -1;
    }

    /// <summary>
    /// Aligns the given value to the specified alignment.
    /// </summary>
    public static uint Align(this uint value, uint alignment)
    {
        return (value + alignment - 1) & ~(alignment - 1);
    }

    /// <summary>
    /// Aligns the given value to the specified alignment.
    /// </summary>
    public static int Align(this int value, int alignment)
    {
        return (value + alignment - 1) & ~(alignment - 1);
    }


}
